package listbyorder.access301_400.test378;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/1 23:03
 */
public class Solution2 {

    // 方法二 ： 改变数组
    public int kthSmallest2(int[][] matrix, int k) {
        int n = matrix.length - 1;
        int left = matrix[0][0];
        int right = matrix[n][n];
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 黑盒， 获取当前mid在数组中的位置
            int count = countNotMoreThanMid(matrix, mid, n);
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private int countNotMoreThanMid(int[][] matrix, int mid, int n) {
        int count = 0;
        int x = 0, y = n;
        while (x <= n && y >= 0) {
            if (matrix[y][x] <= mid) {
                count += y + 1;
                x++;
            } else {
                y--;
            }
        }
        return count;
    }

}
